package com.leetcode.q954;

import java.util.*;
import java.util.stream.Collectors;

/**
 * <p> description: 二倍数对数组
 *
 * 对于一个偶数长度数组，每一组由相邻[奇位，偶位]的数对来说，都有偶位=2*奇位，则认为这个数组可以作为二倍数对数组
 *
 * 判断一个偶数长度数组，经过重组后能够成为二倍数对数组
 *
 * </p>
 *
 * @author tanzc
 * @date 2022/4/1
 **/
public class CanReorderDoubled {
    public boolean canReorderDoubledBak(int[] arr) {
        Map<Integer, Integer> map = new LinkedHashMap<>();
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(arr[i]);
            map.merge(arr[i], 1, Integer::sum);
        }
        Set<Integer> set = list.stream().sorted(Comparator.comparingInt(o -> Math.abs(o))).collect(Collectors.toCollection(LinkedHashSet::new));
        for (Integer num : set) {
            while (map.get(num) != 0) {
                int dNum = map.getOrDefault(num * 2, 0);
                if (dNum == 0) {
                    return false;
                }
                map.put(num, map.get(num) - 1);
                map.put(num * 2, dNum - 1);
            }
        }
        return true;
    }


    public boolean canReorderDoubled(int[] arr) {
        Arrays.sort(arr);
        //if (arr[0] == arr[arr.length - 1] && arr[0] == 0) return true;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : arr) {
            if (i < 0) {
                // 有2倍，则2倍的减1
                if (map.containsKey(2 * i) && map.get(2 * i) != 0) {
                    map.put(2 * i, map.get(2 * i) - 1);
                } else {
                    // 没2倍，则自己加1
                    map.put(i, map.getOrDefault(i, 0) + 1);
                }
            }
            else {
                if (map.containsKey(i) && map.get(i) != 0) {
                    map.put(i, map.get(i) - 1);
                } else {
                    map.put(2 * i, map.getOrDefault(2 * i, 0) + 1);
                }
            }
        }
        for (int i : map.values()) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        CanReorderDoubled canReorderDoubled = new CanReorderDoubled();
        System.out.println(canReorderDoubled.canReorderDoubled(new int[]{-8,-4,-2,-1,1,2,4,8}));
    }
}
